Aesthetical criteria for drawing trees

One of the most commonly used data structures in computer science is the tree. As many people are using trees in their research or just as illustration tools, they are usually struggling with the problem of drawing trees. We are concerned primarily with ordered trees in the sense of [9], especially binary and unary-binary trees. A binary tree is a finite set of nodes which either is empty, or consists of a root and two disjoint binary trees called the left and right subtrees of the root. A unary-binary tree is a finite set of nodes which either is empty, or consists of a root and two disjoint unary-binary trees, or consists of a root and one nonempty unary-binary tree. An extended binary tree is a binary tree in which each node has either two nonempty subtrees or two empty subtrees.

For these trees there are some basic agreements on how they should be drawn, reflecting the top-down and left-right ordering of nodes in a tree; see [15] and [17].

1.

Trees impose a distance on the nodes; no node should be closer to the root than any of its ancestors.

2.

Nodes of a tree at the same height should lie on a straight line, and the straight lines defining the levels should be parallel.

3.

The relative order of nodes on any level should be the same as in the level order traversal of the tree.

These axioms guarantee that trees are drawn as planar graphs: edges do not intersect except at nodes. Two further axioms improve the aesthetical appearance of trees:

4.

In a unary-binary tree, each left child should be positioned to the left of its parent, each right child to the right of its parent, and each unary child should be positioned below its parent.

5.

A parent should be centered over its children.

An additional axiom deals with the problem of tree drawings becoming too wide and therefore exceeding the physical limit of the output medium:

6.

Tree drawings should occupy as little width as possible without violating the other axioms.

In [17], Wetherell and Shannon introduce two algorithms for tree drawings, the first of which fulfills axioms 1–5, and the second 1–6. However, as Reingold and Tilford in [15] point out, there is a lack of symmetry in the algorithms of Wetherell and Shannon which may lead to unpleasant results. Therefore, Reingold and Tilford introduce a new structured axiom:

7.

A subtree of a given tree should be drawn the same way regardless of where it occurs in the given tree.

Axiom 7 allows the same tree to be drawn differently when it occurs as a subtree in different trees. Reingold and Tilford give an algorithm which fulfills axioms 1–5 and 7. Although this algorithm doesn't fulfill axiom 6, the aesthetical improvements are well worth the additional space. Figure  illustrates the benefits of axiom 7, and Figure  shows that the algorithm of Reingold and Tilford violates axiom 6.

Figure: The left tree is drawn by the algorithm of Wetherell and Shannon, and the tidier right one is drawn by the algorithm of Reingold and Tilford.
Figure: The left tree is drawn by the algorithm of Reingold and Tildford, but the right tree shows that narrower drawings fulfilling all aesthetic axioms are possible.